Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.     

OLAP query reformulation in peer-to-peer data warehousing

Inter-business collaborative contexts prefigure a distributed scenario where companies organize and coordinate themselves to develop common and shared opportunities, but traditional business intelligence systems do not provide support to this end. To fill this gap, in this paper we envision a peer-to-peer data warehousing architecture based on a network of heterogeneous peers, each exposing query answering functionalities aimed at sharing business information. To enhance the decision making process, an OLAP query expressed on a peer needs to be properly reformulated on the local multidimensional schemata of the other peers. To this end, we present a language for the definition of mappings between the multidimensional schemata of peers and we introduce a query reformulation framework that relies on the translation of mappings, queries, and multidimensional schemata onto the relational level. Then, we formalize a query reformulation algorithm and prove two properties: correctness and closure, that are essential in a peer-to-peer setting. Finally, we discuss the main implementation issues related to the reformulation setting proposed, with specific reference to the case in which the local multidimensional engines hosted by peers use the standard MDX language.     

Ontological query answering under expressive Entity-Relationship schemata

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity-Relationship model. This extended model, called ER⁺, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER⁺ schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER⁺. We provide a precise syntactic characterization of separable ER⁺ schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER⁺ schemata, and also under several sublanguages of ER⁺. We show that the addition of so-called negative constraints does not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely adopted tractable ontology languages, including those in the DL-Lite family.     

一种基于哈希索引的内存表模型

介绍一种基于哈希索引的内存表模型。该模型能有效提高应用系统参数查询的效率,从而提升应用系统处理性能。     

需求概念图导引下的网页检索结果过滤

基于关键词的布尔模型将用户需求视为词汇集合,只考虑词汇共现,忽略了词汇间的概念关联,用于信息检索精确度较低。基于概念图的内涵模型重建词汇间的概念关联,更好地反映用户需求,有望提高检索精确度。提出一种在需求概念图导引下对网页检索结果进行过滤的方法:给定需求概念图,在摘要中寻找需求概念图包含的概念及其关联,构建简化的摘要概念图,如果简化的摘要概念图能够覆盖需求概念图,则保留该摘要,否则将该摘要滤除。     

一种TCP友好的无线多跳网络拥塞控制算法

为了改进流媒体在无线多跳网络中的传输质量,提出一种TCP友好的拥塞控制算法.该算法考虑了MAC层的信道竞争,节点通过标记数据包来通知数据流它的竞争状态,数据流基于所估计的竞争状态来控制传输速率.仿真结果表明所提出的算法能更有效地利用带宽,与已存在的算法相比,有较高的吞吐量和较好的平滑性.     

动态更新实物化视图以提高OLAP查询效率

在数据仓库系统中,OLAP查询一般都涉及多表连接和分组聚集两部分操作,提高这些查询的性能成为提高OLAP响应速度的关键。利用实物化视图,可以准确地计算并保存表连接或聚集等耗时较多的操作的结果。研究基于查询频率的实物化视图的更新算法,可以使实物化视图得到最大效率的使用,明显地缩短查询的响应时间,从而提高OLAP的查询效率。     

集合特征码及相关算法研究

在传统的集合运算过程中,集合内的元素一般通过自然语言表示,而不是形式化表示,这就在计算机处理时影响了集合运算的效率。为了解决这个问题,将二进制引入到集合运算过程中,提出集合特征码的概念,并定义了一系列的集合特征码运算规则,从而形成了一个较为完备的、形式化的集合特征码运算体系。在上述集合特征码的理论体系下,提出一系列的相关算法,从而在算法的层次上实现了集合特征码的理论体系。实验结果表明,通过集合特征码理论及相关算法,集合运算可以通过0、1运算快速实现,并且其成功实现了数据库中的查询操作。     

一种基于XML小枝查询片段松弛的近似查询与结果排序方法

提出了一种基于XML小枝查询片段松弛的近似查询与结果排序方法来实现用户在XML文档中的近似查询:通过收集用户的查询历史来推测用户偏好,并以此计算原始小枝查询分解得到的查询片段的重要程度,然后按照重要程度的排序进行查询松弛;在松弛方法中,根据查询片段数目的不同采用不同的松弛方法,若片段数目较多则以查询片段为粒度对其松弛,较少则以查询结点为粒度对数值查询与非数值查询采用不同的方法进行松弛,得到最为相关的近似查询结果;最后按近似查询结果对原始查询和用户偏好的满足程度进行排序并输出。实验证明,该近似查询方法能够较好地满足用户的需求和偏好,具有较高的查全率和准确率。     

基于用户查询意图识别的Web搜索优化模型

在对用户查询意图进行分析分类的基础上,提出了一种Web搜索优化模型。该模型通过识别用户查询意图来查询意图特征词和内容主题词的双重约束,再结合用户查询行为获得查询目标,既保证了用户查询意图的准确匹配,又自动过滤和屏蔽了不相关信息。与相关工作对比,其重点在于准确获取用户查询意图,提高用户满意度。实验结果表明,该模型在实现信息搜索准确性和用户对查询结果满意度方面比传统搜索方法有明显改善。